package Offer496;

import java.util.HashMap;
import java.util.Stack;

/**
 * 给你两个 没有重复元素 的数组nums1 和nums2，其中nums1nums2的子集。
 *
 * 请你找出 nums1中每个元素在nums2中的下一个比其大的值。
 *
 * nums1中数字x的下一个更大元素是指x在nums2中对应位置的右边的第一个比x大的元素。如果不存在，对应位置输出 -1 。
 * @author 23737
 * @time 2021.10.26
 */
public class Test {
    public static void main(String[] args) {
        int[] a = new int[]{4,1,2};
        int[] b = new int[]{1,3,4,2};
        int[] ints = new Solution().nextGreaterElement(a, b);
        for (int i = 0; i < ints.length; i++) {
            System.out.println(ints[i]);
        }
    }
}

/**
 * 栈和哈希表
 */
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> stack = new Stack<Integer>();
        HashMap<Integer, Integer> hasMap = new HashMap<Integer, Integer>();

        int[] result = new int[nums1.length];

        for(int num : nums2) {
            while(!stack.isEmpty() && stack.peek()<num){
                hasMap.put(stack.pop(), num);
            }
            stack.push(num);
        }

        for(int i = 0; i < nums1.length; i++) result[i] = hasMap.getOrDefault(nums1[i], -1);

        return result;
    }
}


